package algorithm_demo.demo04.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Dijkstra算法,不能存在负值的边
 *
 * @author Api
 * @date 2023/2/26 13:19
 */
public class Code06_Dijkstra {
    /*
     * Dijkstra算法
     * 1. Dijkstra算法必须指定一个源点
     * 2. 生成一个源点到各个点的最小距离表，一开始只有一条记录，即源点到自己的最小距离为0，
     * 源点到其他所有点的最小距离都为正无穷大
     * 3. 从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，
     * 不断重复这一步
     * 4. 源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了。
     * */

    public static Map<Node, Integer> dijkstra1(Node head) {
        //从head出发到所有点的最小距离
        //key：从head出发到达key
        //value：从head出发到达key的最小距离
        //如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
        Map<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        //已经求过距离的节点，存在selectedNodes中，以后再也不碰
        Set<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            int distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    public static Node getMinDistanceAndUnselectedNode(Map<Node, Integer> distanceMap, Set<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    //----------------------------------------------------------------------------------------------------
    public static class NodeRecord {
        public Node node;

        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }


    public static class NodeHeap{
        private Node[] nodes;//实际的堆结构
        //key某一个node，value上面堆中的位置
        private Map<Node, Integer> heapIndexMap;
        //key某一个节点，value从源节点出发到该节点的目前最小距离
        private Map<Node, Integer> distanceMap;
        private int size;//堆上有多少个点

        public NodeHeap(int size){
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            size = 0;
        }

        public boolean isEmpty(){
            return size==0;
        }

        //有一个点叫node,现在发现了从源节点出发到达node的距离为distance
        //判断要不要更新，如果需要的话，就更新
        public void addOrUpdateOrIgnore(Node node, int distance){
            if (inHeap(node)) {
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                insertHeapify(heapIndexMap.get(node));
            }
            if (!isEntered(node)) {
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(size++);
            }
        }

        private boolean inHeap(Node node){
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }

        private void insertHeapify(int index) {
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }


        private void swap(int index1, int index2){
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }

        private boolean isEntered(Node node){
            return heapIndexMap.containsKey(node);
        }


        //弹出
        public NodeRecord pop(){
            NodeRecord  nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            swap(0, size-1);
            heapIndexMap.put(nodes[size-1], -1);
            distanceMap.remove(nodes[size-1]);
            nodes[size-1] = null;
            heapify(0, --size);
            return nodeRecord;
        }

        public void heapify(int index, int size){
            int left = index *2+1;
            while(left<size){
                int smallest = left+1<size && distanceMap.get(nodes[left+1])<distanceMap.get(nodes[left])
                    ? left+1
                    : left;
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                if (smallest == index) {
                    break;
                }
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }
    }


    //改进后的dijkstra算法
    //从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
    public static Map<Node, Integer> dijkstra2(Node head, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        Map<Node, Integer> result = new HashMap<>();
        while(!nodeHeap.isEmpty()){
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;
            int distance = record.distance;
            for(Edge edge:cur.edges){
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight+distance);
            }
            result.put(cur,distance);
        }
        return result;
    }
}
